home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqbuild / rad.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  43.9 KB  |  1,835 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. vec3_t *texreflectivity;
  5. vec3_t *radiosity;
  6. vec3_t *illumination;
  7. struct patch **facepatches;
  8. struct entity **faceentity;
  9. struct patch *patches;
  10. int numpatches = 0;
  11. struct dplane_t *backplanes;
  12. int fakeplanes;
  13. int *leafparents;
  14. int *nodeparents;
  15. float subdiv = 64;
  16. struct directlight **directlights;
  17. struct facelight *facelights;
  18. int numdlights = 0;
  19. int numbounce = 8;
  20. bool dumppatches;
  21. int junk;
  22. float ambient = 0;
  23. float maxlight = 196;
  24. float lightscale = 1.0;
  25. float direct_scale = 0.4;
  26. float entity_scale = 1.0;
  27.  
  28. extern struct tnode *tnodes, *tnode_p;
  29. int TestLine_r(register int node, vec3_t start, vec3_t stop)
  30. {
  31.   struct tnode *tnode;
  32.   float front, back;
  33.   vec3_t mid;
  34.   float frac;
  35.   int side;
  36.   int r;
  37.  
  38.   if (node & (1 << 31))
  39.     return node & ~(1 << 31);                               // leaf node
  40.  
  41.   tnode = &tnodes[node];
  42.   switch (tnode->type) {
  43.     case PLANE_X:
  44.       front = start[0] - tnode->dist;
  45.       back = stop[0] - tnode->dist;
  46.       break;
  47.     case PLANE_Y:
  48.       front = start[1] - tnode->dist;
  49.       back = stop[1] - tnode->dist;
  50.       break;
  51.     case PLANE_Z:
  52.       front = start[2] - tnode->dist;
  53.       back = stop[2] - tnode->dist;
  54.       break;
  55.     default:
  56.       front = DotProduct(start, tnode->normal) - tnode->dist;
  57.       back = DotProduct(stop, tnode->normal) - tnode->dist;
  58.      //
  59.      // front = (start[0] * tnode->normal[0] + start[1] * tnode->normal[1] + start[2] * tnode->normal[2]) - tnode->dist;
  60.      // back = (stop[0] * tnode->normal[0] + stop[1] * tnode->normal[1] + stop[2] * tnode->normal[2]) - tnode->dist;
  61.      //
  62.       break;
  63.   }
  64.  
  65.   if (front >= -ON_EPSILON && back >= -ON_EPSILON)
  66.     return TestLine_r(tnode->children[0], start, stop);
  67.  
  68.   if (front < ON_EPSILON && back < ON_EPSILON)
  69.     return TestLine_r(tnode->children[1], start, stop);
  70.  
  71.   side = front < 0;
  72.  
  73.   frac = front / (front - back);
  74.  
  75.   mid[0] = start[0] + (stop[0] - start[0]) * frac;
  76.   mid[1] = start[1] + (stop[1] - start[1]) * frac;
  77.   mid[2] = start[2] + (stop[2] - start[2]) * frac;
  78.  
  79.   if((r = TestLine_r(tnode->children[side], start, mid)))
  80.     return r;
  81.   else
  82.     return TestLine_r(tnode->children[!side], mid, stop);
  83. }
  84.  
  85. /*
  86.  * =============
  87.  * CollectLight
  88.  * =============
  89.  */
  90. float CollectLight(void)
  91. {
  92.   int i, j;
  93.   struct patch *patch;
  94.   vec_t total;
  95.  
  96.   total = 0;
  97.  
  98.   for (i = 0, patch = patches; i < numpatches; i++, patch++) {
  99.     // skys never collect light, it is just dropped
  100.     if (patch->sky) {
  101.       VectorClear(radiosity[i]);
  102.       VectorClear(illumination[i]);
  103.       continue;
  104.     }
  105.  
  106.     for (j = 0; j < 3; j++) {
  107.       patch->totallight[j] += illumination[i][j] / patch->area;
  108.       radiosity[i][j] = illumination[i][j] * patch->reflectivity[j];
  109.     }
  110.  
  111.     total += radiosity[i][0] + radiosity[i][1] + radiosity[i][2];
  112.     VectorClear(illumination[i]);
  113.   }
  114.  
  115.   return total;
  116. }
  117.  
  118. /*
  119.  * =============
  120.  * ShootLight
  121.  * 
  122.  * Send light out to other patches
  123.  * Run multi-threaded
  124.  * =============
  125.  */
  126. void ShootLight(register int patchnum)
  127. {
  128.   int k, l;
  129.   struct transfer *trans;
  130.   int num;
  131.   struct patch *patch;
  132.   vec3_t send;
  133.  
  134.   // this is the amount of light we are distributing
  135.   // prescale it so that multiplying by the 16 bit
  136.   // transfer values gives a proper output value
  137.   for (k = 0; k < 3; k++)
  138.     send[k] = radiosity[patchnum][k] / 0x10000;
  139.   patch = &patches[patchnum];
  140.  
  141.   trans = patch->transfers;
  142.   num = patch->numtransfers;
  143.  
  144.   for (k = 0; k < num; k++, trans++) {
  145.     for (l = 0; l < 3; l++)
  146.       illumination[trans->patch][l] += send[l] * trans->transfer;
  147.   }
  148. }
  149.  
  150. /*
  151.  * =============
  152.  * BounceLight
  153.  * =============
  154.  */
  155. void BounceLight(void)
  156. {
  157.   int i, j;
  158.   float added;
  159.   struct patch *p;
  160.  
  161.   for (i = 0; i < numpatches; i++) {
  162.     p = &patches[i];
  163.     for (j = 0; j < 3; j++) {
  164. //                      p->totallight[j] = p->samplelight[j];
  165.       radiosity[i][j] = p->samplelight[j] * p->reflectivity[j] * p->area;
  166.     }
  167.   }
  168.  
  169.   for (i = 0; i < numbounce; i++) {
  170.     for (j = 0; j < numpatches; j++)
  171.       ShootLight(j);
  172.  
  173.     added = CollectLight();
  174.     mprintf("    - bounce %i\n%5i added\n", i, added);
  175.   }
  176. }
  177.  
  178. void ClearLBounds (vec3_t mins, vec3_t maxs)
  179. {
  180.   mins[0] = mins[1] = mins[2] = 99999;
  181.   maxs[0] = maxs[1] = maxs[2] = -99999;
  182. }
  183.  
  184. void AddPointToBounds (vec3_t v, vec3_t mins, vec3_t maxs)
  185. {
  186.   int i;
  187.   vec_t val;
  188.  
  189.   for (i=0 ; i<3 ; i++) {
  190.     val = v[i];
  191.     if (val < mins[i])
  192.       mins[i] = val;
  193.     if (val > maxs[i])
  194.       maxs[i] = val;
  195.   }
  196. }
  197.  
  198. /*
  199.  * ===================================================================
  200.  * 
  201.  * TEXTURE LIGHT VALUES
  202.  * 
  203.  * ===================================================================
  204.  */
  205.  
  206. vec_t ColorNormalize (vec3_t in, vec3_t out)
  207. {
  208.   float max;
  209.  
  210.   max = in[0];
  211.   if (in[1] > max) max = in[1];
  212.   if (in[2] > max) max = in[2];
  213.  
  214.   if (max != 0)
  215.     VectorScale (in, 1.0 / max, out);
  216.  
  217.   return max;
  218. }
  219.  
  220. /*
  221.  * ======================
  222.  * CalcTextureReflectivity
  223.  * ======================
  224.  */
  225. void CalcTextureReflectivity(__memBase)
  226. {
  227.   int i, j;
  228.   struct rgb *palette;
  229.   struct dmiptexlump_t *l = (struct dmiptexlump_t *)bspMem->dtexdata;
  230.  
  231.   if(!(palette = GetPalette()))
  232.     Error("CalcTextureRefletivity: failed to load palette\n");
  233.  
  234.   // allways set index 0 even if no textures
  235.   texreflectivity[0][0] = 0.5;
  236.   texreflectivity[0][1] = 0.5;
  237.   texreflectivity[0][2] = 0.5;
  238.  
  239.   for (i = 0; i < bspMem->numtexinfo; i++) {
  240.     struct texinfo *curtex = &bspMem->texinfo[i];
  241.   
  242.     // see if an earlier texinfo allready got the value
  243.     for (j = 0; j < i; j++) {
  244.       if (curtex->miptex == bspMem->texinfo[j].miptex) {
  245.     VectorCopy(texreflectivity[j], texreflectivity[i]);
  246.     break;
  247.       }
  248.     }
  249.     
  250.     if (j == i) {
  251.       struct mipmap *mt = (struct mipmap *)(l->dataofs[curtex->miptex] + (int)l);
  252.       int texels = mt->width * mt->height;
  253.       unsigned char texel;
  254.       unsigned char *body = (unsigned char *)mt + mt->offsets[MIPMAP_0];
  255.       int color[3] = {0, 0, 0};
  256.       float scale;
  257.  
  258.       for (j = 0; j < texels; j++) {
  259.         texel = *body++;
  260.         color[0] += palette[texel].r;
  261.         color[1] += palette[texel].g;
  262.         color[2] += palette[texel].b;
  263.       }
  264.  
  265.       for (j = 0; j < 3; j++) {
  266.         float r = color[j] / texels / 255.0;
  267.         texreflectivity[i][j] = r;
  268.       }
  269.     
  270.       mprintf("%s has a reflectivity of (%f,%f,%f)\n", mt->name, texreflectivity[i][0], texreflectivity[i][1], texreflectivity[i][2]);
  271.     
  272.       // scale the reflectivity up, because the textures are
  273.       // so dim
  274.       scale = ColorNormalize(texreflectivity[i], texreflectivity[i]);
  275.       if (scale < 0.5) {
  276.         scale *= 2;
  277.         VectorScale(texreflectivity[i], scale, texreflectivity[i]);
  278.       }
  279.     }
  280.   }
  281. }
  282.  
  283. /*
  284.  * ===================
  285.  * DecompressVis
  286.  * ===================
  287.  */
  288. void DecompressVis(__memBase, register unsigned char *in, register unsigned char *decompressed)
  289. {
  290.   int c;
  291.   int row;
  292.   unsigned char *out;
  293.  
  294.   row = (bspMem->numleafs + 7) >> 3;
  295.   out = decompressed;
  296.  
  297.   do {
  298.     if (*in) {
  299.       *out++ = *in++;
  300.       continue;
  301.     }
  302.  
  303.     c = in[1];
  304.     in += 2;
  305.     while (c) {
  306.       *out++ = 0;
  307.       c--;
  308.     }
  309.   } while (out - decompressed < row);
  310. }
  311.  
  312. int PointInLeafNum(__memBase, vec3_t point)
  313. {
  314.   int nodenum;
  315.   vec_t dist;
  316.   struct dnode_t *node;
  317.   struct dplane_t *plane;
  318.  
  319.   nodenum = 0;
  320.   while (nodenum >= 0) {
  321.     node = &bspMem->dnodes[nodenum];
  322.     plane = &bspMem->dplanes[node->planenum];
  323.     dist = DotProduct(point, plane->normal) - plane->dist;
  324.     if (dist > 0)
  325.       nodenum = node->children[0];
  326.     else
  327.       nodenum = node->children[1];
  328.   }
  329.  
  330.   return -nodenum - 1;
  331. }
  332.  
  333. bool PvsForOrigin(__memBase, vec3_t org, register unsigned char *pvs)
  334. {
  335.   if (!bspMem->visdatasize) {
  336.     memset(pvs, 255, (bspMem->numleafs + 7) >> 3);
  337.   }
  338.   else {
  339.     struct dleaf_t *leaf = &bspMem->dleafs[PointInLeafNum(bspMem, org)];
  340.     DecompressVis(bspMem, bspMem->dvisdata + leaf->visofs, pvs);
  341.   }
  342.   
  343.   return TRUE;
  344. }
  345.  
  346. /*
  347.  * =============
  348.  * MakeBackplanes
  349.  * =============
  350.  */
  351. void MakeBackPlanes(__memBase)
  352. {
  353.   int i;
  354.  
  355.   for (i = 0; i < bspMem->numplanes; i++) {
  356.     backplanes[i].dist = -bspMem->dplanes[i].dist;
  357.     VectorNegateTo(bspMem->dplanes[i].normal, backplanes[i].normal);
  358.   }
  359. }
  360.  
  361. /*
  362.  * =============
  363.  * MakeParents
  364.  * =============
  365.  */
  366. void MakeParents(__memBase, register int nodenum, register int parent)
  367. {
  368.   int i, j;
  369.   struct dnode_t *node;
  370.  
  371.   nodeparents[nodenum] = parent;
  372.   node = &bspMem->dnodes[nodenum];
  373.  
  374.   for (i = 0; i < 2; i++) {
  375.     j = node->children[i];
  376.     if (j < 0)
  377.       leafparents[-j - 1] = nodenum;
  378.     else
  379.       MakeParents(bspMem, j, nodenum);
  380.   }
  381. }
  382.  
  383. /*
  384.  * =============
  385.  * MakePatchForFace
  386.  * =============
  387.  */
  388.  
  389. bool IsSky(__memBase, register struct dface_t * f)
  390. {
  391.   struct texinfo *tx;
  392.   struct mipmap *mt;
  393.   struct dmiptexlump_t *l = (struct dmiptexlump_t *)bspMem->dtexdata;
  394.  
  395.   tx = &bspMem->texinfo[f->texinfo];
  396.   mt = (struct mipmap *)(l->dataofs[tx->miptex] + (int)l);
  397.   if(!strcmp(mt->name, "sky"))
  398.     return TRUE;
  399.   return FALSE;
  400. }
  401.  
  402. #define    MAX_PATCHES        4096
  403. float totalarea;
  404. void MakePatchForFace(__memBase, register int facenum, register struct winding *w)
  405. {
  406.   struct dface_t *f;
  407.   float area;
  408.   struct patch *patch;
  409.   struct dplane_t *pl;
  410.   int i;
  411.   vec3_t color;
  412.   struct dleaf_t *leaf;
  413.  
  414.   f = &bspMem->dfaces[facenum];
  415.  
  416.   area = WindingArea(w);
  417.   totalarea += area;
  418.  
  419.   patch = &patches[numpatches];
  420.   if (numpatches == MAX_PATCHES)
  421.     Error("numpatches == MAX_PATCHES\n");
  422.   patch->next = facepatches[facenum];
  423.   facepatches[facenum] = patch;
  424.  
  425.   patch->winding = w;
  426.  
  427.   if (f->side)
  428.     patch->plane = &backplanes[f->planenum];
  429.   else
  430.     patch->plane = &bspMem->dplanes[f->planenum];
  431.   if (faceoffset[facenum][0] || faceoffset[facenum][1] || faceoffset[facenum][2]) {           // origin offset faces must create new planes
  432.     if(bspMem->numplanes + fakeplanes >= bspMem->max_numplanes)
  433.       ExpandClusters(bspMem, LUMP_PLANES);
  434.     pl = &bspMem->dplanes[bspMem->numplanes + fakeplanes];
  435.     fakeplanes++;
  436.  
  437.     *pl = *(patch->plane);
  438.     pl->dist += DotProduct(faceoffset[facenum], pl->normal);
  439.     patch->plane = pl;
  440.   }
  441.  
  442.   WindingCenter(w, patch->origin);
  443.   VectorAdd(patch->origin, patch->plane->normal, patch->origin);
  444.   leaf = &bspMem->dleafs[PointInLeafNum(bspMem, patch->origin)];
  445.   patch->cluster = leaf->visofs;
  446.   patch->area = area;
  447.   if (patch->area <= 1)
  448.     patch->area = 1;
  449.   patch->sky = IsSky(bspMem, f);
  450.  
  451.   VectorCopy(texreflectivity[f->texinfo], patch->reflectivity);
  452.  
  453.   // non-bmodel patches can emit light
  454.   if (facenum < bspMem->dmodels[0].numfaces) {
  455.     VectorClear(patch->baselight);
  456.     ColorNormalize(patch->reflectivity, color);
  457.     for (i = 0; i < 3; i++)
  458.       patch->baselight[i] *= color[i];
  459.     VectorCopy(patch->baselight, patch->totallight);
  460.   }
  461.   numpatches++;
  462. }
  463.  
  464. /*
  465.  * =============
  466.  * MakePatches
  467.  * =============
  468.  */
  469. void MakePatches(__memBase)
  470. {
  471.   int i, j, k;
  472.   struct dface_t *f;
  473.   int start;
  474.   struct winding *w;
  475.   struct dmodel_t *mod;
  476.   struct entity *ent;
  477.  
  478.   mprintf("%5i faces\n", bspMem->numfaces);
  479.  
  480.   for (i = 0; i < bspMem->nummodels; i++) {
  481.     mod = &bspMem->dmodels[i];
  482.     ent = FindEntityWithModel(bspMem, i);
  483.     // bmodels with origin brushes need to be offset into their
  484.     // in-use position
  485.     start = mod->firstface;
  486.     for (j = start; j < start + mod->numfaces; j++) {
  487.       VectorCopy(ent->origin, faceoffset[j]);
  488.       faceentity[j] = ent;
  489.       f = &bspMem->dfaces[j];
  490.       w = WindingFromFace(bspMem, f);
  491.       for (k = 0; k < w->numpoints; k++) {
  492.     VectorAdd(w->points[k], ent->origin, w->points[k]);
  493.       }
  494.       MakePatchForFace(bspMem, j, w);
  495.     }
  496.   }
  497.  
  498.   mprintf("%5i square feet\n", (int)(totalarea / 64));
  499. }
  500.  
  501. void CheckPatches(void)
  502. {
  503.   int i;
  504.   struct patch *patch;
  505.  
  506.   for (i = 0; i < numpatches; i++) {
  507.     patch = &patches[i];
  508.     if (patch->totallight[0] < 0 || patch->totallight[1] < 0 || patch->totallight[2] < 0)
  509.       Error("negative patch totallight\n");
  510.   }
  511. }
  512.  
  513. /*
  514.  * =============
  515.  * MakeTransfers
  516.  * 
  517.  * =============
  518.  */
  519. int total_transfer;
  520.  
  521. void MakeTransfers(__memBase, register int i)
  522. {
  523.   int j;
  524.   vec3_t delta;
  525.   vec_t dist, scale;
  526.   float trans;
  527.   int itrans;
  528.   struct patch *patch, *patch2;
  529.   float total;
  530.   struct dplane_t plane;
  531.   vec3_t origin;
  532.   float transfers[MAX_PATCHES], *all_transfers;
  533.   int itotal;
  534.   unsigned char pvs[(MAX_MAP_LEAFS + 7) / 8];
  535.   int cluster;
  536.  
  537.   patch = patches + i;
  538.   total = 0;
  539.  
  540.   VectorCopy(patch->origin, origin);
  541.   plane = *patch->plane;
  542.  
  543.   if (!PvsForOrigin(bspMem, patch->origin, pvs))
  544.     return;
  545.  
  546.   // find out which patch2s will collect light
  547.   // from patch
  548.  
  549.   all_transfers = transfers;
  550.   patch->numtransfers = 0;
  551.   for (j = 0, patch2 = patches; j < numpatches; j++, patch2++) {
  552.     transfers[j] = 0;
  553.  
  554.     if (j == i)
  555.       continue;
  556.  
  557.     // check pvs bit
  558.     if (!bspMem->visdatasize) {
  559.       cluster = patch2->cluster;
  560.       if (cluster == -1)
  561.     continue;
  562.       if (!(pvs[cluster >> 3] & (1 << (cluster & 7))))
  563.     continue;                                   // not in pvs
  564.     }
  565.  
  566.     // calculate vector
  567.     VectorSubtract(patch2->origin, origin, delta);
  568.     dist = VectorNormalize(delta);
  569.     if (!dist)
  570.       continue;                                       // should never happen
  571.  
  572.     // reletive angles
  573.     scale = DotProduct(delta, plane.normal);
  574.     scale *= -DotProduct(delta, patch2->plane->normal);
  575.     if (scale <= 0)
  576.       continue;
  577.  
  578.     // check exact tramsfer
  579.     if (TestLine_r(0, patch->origin, patch2->origin))
  580.       continue;
  581.  
  582.     trans = scale * patch2->area / (dist * dist);
  583.  
  584.     if (trans < 0)
  585.       trans = 0;                                   // rounding errors...
  586.  
  587.     transfers[j] = trans;
  588.     if (trans > 0) {
  589.       total += trans;
  590.       patch->numtransfers++;
  591.     }
  592.   }
  593.  
  594.   // copy the transfers out and normalize
  595.   // total should be somewhere near PI if everything went right
  596.   // because partial occlusion isn't accounted for, and nearby
  597.   // patches have underestimated form factors, it will usually
  598.   // be higher than PI
  599.   if (patch->numtransfers) {
  600.     struct transfer *t;
  601.  
  602.     if (patch->numtransfers < 0 || patch->numtransfers > MAX_PATCHES)
  603.       Error("Weird numtransfers\n");
  604.     if(!(patch->transfers = (struct transfer *)tmalloc(patch->numtransfers * sizeof(struct transfer))))
  605.       Error("MakeTransfers: failed to allocate transfer!\n");
  606.  
  607.     //
  608.     // normalize all transfers so all of the light
  609.     // is transfered to the surroundings
  610.     //
  611.     t = patch->transfers;
  612.     itotal = 0;
  613.     for (j = 0; j < numpatches; j++) {
  614.       if (transfers[j] <= 0)
  615.     continue;
  616.       itrans = transfers[j] * 0x10000 / total;
  617.       itotal += itrans;
  618.       t->transfer = itrans;
  619.       t->patch = j;
  620.       t++;
  621.     }
  622.   }
  623.  
  624.   // don't bother locking around this.  not that important.
  625.   total_transfer += patch->numtransfers;
  626. }
  627.  
  628. /*
  629.  * =============
  630.  * FreeTransfers
  631.  * =============
  632.  */
  633. void FreeTransfers(void)
  634. {
  635.   int i;
  636.  
  637.   for (i = 0; i < numpatches; i++) {
  638.     tfree(patches[i].transfers);
  639.     patches[i].transfers = NULL;
  640.   }
  641. }
  642.  
  643. /*
  644.  * =======================================================================
  645.  * 
  646.  * SUBDIVIDE
  647.  * 
  648.  * =======================================================================
  649.  */
  650.  
  651. void FinishSplit(__memBase, register struct patch * patch, register struct patch * newp)
  652. {
  653.   struct dleaf_t *leaf;
  654.  
  655.   VectorCopy(patch->baselight, newp->baselight);
  656.   VectorCopy(patch->totallight, newp->totallight);
  657.   VectorCopy(patch->reflectivity, newp->reflectivity);
  658.   newp->plane = patch->plane;
  659.   newp->sky = patch->sky;
  660.  
  661.   patch->area = WindingArea(patch->winding);
  662.   newp->area = WindingArea(newp->winding);
  663.  
  664.   if (patch->area <= 1)
  665.     patch->area = 1;
  666.   if (newp->area <= 1)
  667.     newp->area = 1;
  668.  
  669.   WindingCenter(patch->winding, patch->origin);
  670.   VectorAdd(patch->origin, patch->plane->normal, patch->origin);
  671.   leaf = &bspMem->dleafs[PointInLeafNum(bspMem, patch->origin)];
  672.   patch->cluster = leaf->visofs;
  673.  
  674.   WindingCenter(newp->winding, newp->origin);
  675.   VectorAdd(newp->origin, newp->plane->normal, newp->origin);
  676.   leaf = &bspMem->dleafs[PointInLeafNum(bspMem, newp->origin)];
  677.   newp->cluster = leaf->visofs;
  678. }
  679.  
  680. /*
  681.  * =============
  682.  * SubdividePatch
  683.  * 
  684.  * Chops the patch only if its local bounds exceed the max size
  685.  * =============
  686.  */
  687. void SubdividePatch(__memBase, register struct patch * patch)
  688. {
  689.   struct winding *w, *o1, *o2;
  690.   vec3_t mins, maxs, total;
  691.   vec3_t split;
  692.   vec_t dist;
  693.   int i, j;
  694.   vec_t v;
  695.   struct patch *newp;
  696.  
  697.   w = patch->winding;
  698.   mins[0] = mins[1] = mins[2] = 99999;
  699.   maxs[0] = maxs[1] = maxs[2] = -99999;
  700.   for (i = 0; i < w->numpoints; i++) {
  701.     for (j = 0; j < 3; j++) {
  702.       v = w->points[i][j];
  703.       if (v < mins[j]) mins[j] = v;
  704.       if (v > maxs[j]) maxs[j] = v;
  705.     }
  706.   }
  707.   VectorSubtract(maxs, mins, total);
  708.   for (i = 0; i < 3; i++)
  709.     if (total[i] > (subdiv + 1))
  710.       // no splitting needed
  711.       return;
  712.  
  713.   //
  714.   // split the winding
  715.   //
  716.   VectorClear(split);
  717.   split[i] = 1;
  718.   dist = (mins[i] + maxs[i]) * 0.5;
  719.   ClipWindingEpsilon(w, split, dist, ON_EPSILON, &o1, &o2);
  720.  
  721.   //
  722.   // create a new patch
  723.   //
  724.   if (numpatches == MAX_PATCHES)
  725.     Error("MAX_PATCHES\n");
  726.   newp = &patches[numpatches];
  727.   numpatches++;
  728.  
  729.   newp->next = patch->next;
  730.   patch->next = newp;
  731.  
  732.   patch->winding = o1;
  733.   newp->winding = o2;
  734.  
  735.   FinishSplit(bspMem, patch, newp);
  736.  
  737.   SubdividePatch(bspMem, patch);
  738.   SubdividePatch(bspMem, newp);
  739. }
  740.  
  741. /*
  742.  * =============
  743.  * DicePatch
  744.  * 
  745.  * Chops the patch by a global grid
  746.  * =============
  747.  */
  748. void DicePatch(__memBase, register struct patch * patch)
  749. {
  750.   struct winding *w, *o1, *o2;
  751.   vec3_t mins, maxs;
  752.   vec3_t split;
  753.   vec_t dist;
  754.   int i;
  755.   struct patch *newp;
  756.  
  757.   w = patch->winding;
  758.   WindingBounds(w, mins, maxs);
  759.   for (i = 0; i < 3; i++)
  760.     if (floor((mins[i] + 1) / subdiv) < floor((maxs[i] - 1) / subdiv))
  761.       break;
  762.   if (i == 3) {
  763.     // no splitting needed
  764.     return;
  765.   }
  766.  
  767.   //
  768.   // split the winding
  769.   //
  770.   VectorClear(split);
  771.   split[i] = 1;
  772.   dist = subdiv * (1 + floor((mins[i] + 1) / subdiv));
  773.   ClipWindingEpsilon(w, split, dist, ON_EPSILON, &o1, &o2);
  774.  
  775.   //
  776.   // create a new patch
  777.   //
  778.   if (numpatches == MAX_PATCHES)
  779.     Error("MAX_PATCHES\n");
  780.   newp = &patches[numpatches];
  781.   numpatches++;
  782.  
  783.   newp->next = patch->next;
  784.   patch->next = newp;
  785.  
  786.   patch->winding = o1;
  787.   newp->winding = o2;
  788.  
  789.   FinishSplit(bspMem, patch, newp);
  790.  
  791.   DicePatch(bspMem, patch);
  792.   DicePatch(bspMem, newp);
  793. }
  794.  
  795. /*
  796.  * =============
  797.  * SubdividePatches
  798.  * =============
  799.  */
  800. void SubdividePatches(__memBase)
  801. {
  802.   int i, num;
  803.  
  804.   if (subdiv < 1)
  805.     return;
  806.  
  807.   num = numpatches;                                   // because the list will grow
  808.  
  809.   for (i = 0; i < num; i++)
  810. //  SubdividePatch (&patches[i]);
  811.     DicePatch(bspMem, &patches[i]);
  812.     
  813.   mprintf("%5i patches after subdivision\n", numpatches);
  814. }
  815.  
  816. /*
  817.  * ================
  818.  * CalcFaceExtents
  819.  * 
  820.  * Fills in s->texmins[] and s->texsize[]
  821.  * also sets exactmins[] and exactmaxs[]
  822.  * ================
  823.  */
  824. void CalcFaceExtentsII(__memBase, register struct lightinfo * l)
  825. {
  826.   struct dface_t *s;
  827.   vec_t mins[2], maxs[2], val;
  828.   int i, j, e;
  829.   struct dvertex_t *v;
  830.   struct texinfo *tex;
  831.   vec3_t vt;
  832.  
  833.   s = l->face;
  834.  
  835.   mins[0] = mins[1] = 999999;
  836.   maxs[0] = maxs[1] = -99999;
  837.  
  838.   tex = &bspMem->texinfo[s->texinfo];
  839.  
  840.   for (i = 0; i < s->numedges; i++) {
  841.     e = bspMem->dsurfedges[s->firstedge + i];
  842.     if (e >= 0)
  843.       v = bspMem->dvertexes + bspMem->dedges[e].v[0];
  844.     else
  845.       v = bspMem->dvertexes + bspMem->dedges[-e].v[1];
  846.  
  847. //              VectorAdd (v->point, l->modelorg, vt);
  848.     VectorCopy(v->point, vt);
  849.  
  850.     for (j = 0; j < 2; j++) {
  851.       val = DotProduct(vt, tex->vecs[j]) + tex->vecs[j][3];
  852.       if (val < mins[j])
  853.     mins[j] = val;
  854.       if (val > maxs[j])
  855.     maxs[j] = val;
  856.     }
  857.   }
  858.  
  859.   for (i = 0; i < 2; i++) {
  860.     l->exactmins[i] = mins[i];
  861.     l->exactmaxs[i] = maxs[i];
  862.  
  863.     mins[i] = floor(mins[i] / 16);
  864.     maxs[i] = ceil(maxs[i] / 16);
  865.  
  866.     l->texmins[i] = mins[i];
  867.     l->texsize[i] = maxs[i] - mins[i];
  868.  
  869.     if (l->texsize[0] * l->texsize[1] > SINGLEMAP / 4)                   // div 4 for extrasamples
  870.       printf("Surface to large to map: %d*%d", l->texsize[0], l->texsize[1]);
  871.   }
  872. }
  873.  
  874. /*
  875.  * =================================================================
  876.  * 
  877.  * LIGHTMAP SAMPLE GENERATION
  878.  * 
  879.  * =================================================================
  880.  */
  881.  
  882. #define    ANGLE_UP    -1
  883. #define    ANGLE_DOWN    -2
  884.  
  885. /*
  886.  * =============
  887.  * CreateDirectLights
  888.  * =============
  889.  */
  890. void CreateDirectLights(__memBase)
  891. {
  892.   int i;
  893.   struct patch *p;
  894.   struct directlight *dl;
  895.   struct dleaf_t *leaf;
  896.   int cluster;
  897.   struct entity *e, *e2;
  898.   float angle;
  899.   char *_color;
  900.   float intensity;
  901.  
  902.   //
  903.   // surfaces
  904.   //
  905.   for (i = 0, p = patches; i < numpatches; i++, p++) {
  906.     if (p->totallight[0] < DIRECT_LIGHT
  907.     && p->totallight[1] < DIRECT_LIGHT
  908.     && p->totallight[2] < DIRECT_LIGHT)
  909.       continue;
  910.  
  911.     if(!(dl = (struct directlight *)tmalloc(sizeof(struct directlight))))
  912.       Error("CreateDirectLights: failed to allocate directlight!\n");
  913.     numdlights++;
  914.  
  915.     VectorCopy(p->origin, dl->origin);
  916.  
  917.     leaf = &bspMem->dleafs[PointInLeafNum(bspMem, dl->origin)];
  918.     cluster = leaf->visofs;
  919.     dl->next = directlights[cluster];
  920.     directlights[cluster] = dl;
  921.  
  922.     dl->type = emit_surface;
  923.     VectorCopy(p->plane->normal, dl->normal);
  924.  
  925.     dl->intensity = ColorNormalize(p->totallight, dl->color);
  926.     dl->intensity *= p->area * direct_scale;
  927.     VectorClear(p->totallight);                               // all sent now
  928.   }
  929.  
  930.   //
  931.   // entities
  932.   //
  933.   for (i = 0; i < bspMem->nummapentities; i++) {
  934.     e = &bspMem->mapentities[i];
  935.     if (strncmp(e->classname, "light", 5))
  936.       continue;
  937.  
  938.     if(!(dl = (struct directlight *)tmalloc(sizeof(struct directlight))))
  939.       Error("CreateDirectLights: failed to allocate directlight!\n");
  940.     numdlights++;
  941.  
  942.     VectorCopy(e->origin, dl->origin);
  943.     dl->style = e->style;
  944.  
  945.     leaf = &bspMem->dleafs[PointInLeafNum(bspMem, dl->origin)];
  946.     cluster = leaf->visofs;
  947.     dl->next = directlights[cluster];
  948.     directlights[cluster] = dl;
  949.  
  950.     intensity = e->light;
  951.     _color = ValueForKey(e, "_color");
  952.     if (_color && _color[1]) {
  953.       sscanf(_color, "%g %g %g", &dl->color[0], &dl->color[1], &dl->color[2]);
  954.       ColorNormalize(dl->color, dl->color);
  955.     }
  956.     else
  957.       dl->color[0] = dl->color[1] = dl->color[2] = 1.0;
  958.     dl->intensity = intensity * entity_scale;
  959.     dl->type = emit_point;
  960.  
  961.     if (e->target || !strcmp(e->target, "light_spot")) {
  962.       dl->type = emit_spotlight;
  963.       dl->stopdot = FloatForKey(e, "_cone");
  964.       if (!dl->stopdot)
  965.     dl->stopdot = 10;
  966.       dl->stopdot = cos(dl->stopdot / 180 * 3.14159);
  967.       if (e->target[0]) {                               // point towards target
  968.     if (!(e2 = e->targetent))
  969.       eprintf("light at (%g %g %g) has missing target\n",
  970.           dl->origin[0], dl->origin[1], dl->origin[2]);
  971.     else {
  972.       VectorSubtract(e2->origin, dl->origin, dl->normal);
  973.       VectorNormalize(dl->normal);
  974.     }
  975.       }
  976.       else {                                       // point down angle
  977.     angle = e->angle;
  978.     if (angle == ANGLE_UP) {
  979.       dl->normal[0] = dl->normal[1] = 0;
  980.       dl->normal[2] = 1;
  981.     }
  982.     else if (angle == ANGLE_DOWN) {
  983.       dl->normal[0] = dl->normal[1] = 0;
  984.       dl->normal[2] = -1;
  985.     }
  986.     else {
  987.       dl->normal[2] = 0;
  988.       dl->normal[0] = cos(angle / 180 * 3.14159);
  989.       dl->normal[1] = sin(angle / 180 * 3.14159);
  990.     }
  991.       }
  992.     }
  993.   }
  994.  
  995.   mprintf("%5i direct lights\n", numdlights);
  996. }
  997.  
  998. /*
  999.  * =============
  1000.  * AddSampleToPatch
  1001.  * 
  1002.  * Take the sample's collected light and
  1003.  * add it back into the apropriate patch
  1004.  * for the radiosity pass.
  1005.  * 
  1006.  * The sample is added to all patches that might include
  1007.  * any part of it.  They are counted and averaged, so it
  1008.  * doesn't generate extra light.
  1009.  * =============
  1010.  */
  1011. void AddSampleToPatch(vec3_t pos, vec3_t color, register int facenum)
  1012. {
  1013.   struct patch *patch;
  1014.   vec3_t mins, maxs;
  1015.   int i;
  1016.  
  1017.   if (numbounce == 0)
  1018.     return;
  1019.   if (color[0] + color[1] + color[2] < 3)
  1020.     return;
  1021.  
  1022.   for (patch = facepatches[facenum]; patch; patch = patch->next) {
  1023.     // see if the point is in this patch (roughly)
  1024.     WindingBounds(patch->winding, mins, maxs);
  1025.     for (i = 0; i < 3; i++) {
  1026.       if (mins[i] > pos[i] + 16)
  1027.     goto nextpatch;
  1028.       if (maxs[i] < pos[i] - 16)
  1029.     goto nextpatch;
  1030.     }
  1031.  
  1032.     // add the sample to the patch
  1033.     patch->samples++;
  1034.     VectorAdd(patch->samplelight, color, patch->samplelight);
  1035.   nextpatch:;
  1036.   }
  1037. }
  1038.  
  1039. /*
  1040.  * =================================================================
  1041.  * 
  1042.  * POINT TRIANGULATION
  1043.  * 
  1044.  * =================================================================
  1045.  */
  1046.  
  1047. struct edgeshare {
  1048.   struct dface_t *faces[2];
  1049.   bool coplanar;
  1050. };
  1051.  
  1052. int *facelinks;            //[MAX_MAP_FACES];
  1053. int *planelinks[2];        //[MAX_MAP_PLANES];
  1054.  
  1055. /*
  1056.  * ============
  1057.  * LinkPlaneFaces
  1058.  * ============
  1059.  */
  1060. void LinkPlaneFaces(__memBase)
  1061. {
  1062.   int i;
  1063.   struct dface_t *f;
  1064.  
  1065.   if(!(facelinks = (int *)kmalloc(bspMem->numfaces * sizeof(int))))
  1066.     Error("LinkPlaneFaces: failed to allocate facelinks!\n");
  1067.   if(!(planelinks[0] = (int *)kmalloc(bspMem->numplanes * sizeof(int))))
  1068.     Error("LinkPlaneFaces: failed to allocate planelinks0!\n");
  1069.   if(!(planelinks[1] = (int *)kmalloc(bspMem->numplanes * sizeof(int))))
  1070.     Error("LinkPlaneFaces: failed to allocate planelinks1!\n");
  1071.     
  1072.   f = bspMem->dfaces;
  1073.   for (i = 0; i < bspMem->numfaces; i++, f++) {
  1074.     facelinks[i] = planelinks[f->side][f->planenum];
  1075.     planelinks[f->side][f->planenum] = i;
  1076.   }
  1077. }
  1078.  
  1079. /*
  1080.  * ============
  1081.  * PairEdges
  1082.  * ============
  1083.  */
  1084. void PairEdges(__memBase)
  1085. {
  1086.   int i, j, k;
  1087.   struct dface_t *f;
  1088.   struct edgeshare *e;
  1089.   struct edgeshare *edgeshare;
  1090.   
  1091.   if(!(edgeshare = (struct edgeshare *)tmalloc(bspMem->numedges * sizeof(struct edgeshare))))
  1092.     Error("PairEdges: failed to allocate edgeshare!\n");
  1093.  
  1094.   f = bspMem->dfaces;
  1095.   for (i = 0; i < bspMem->numfaces; i++, f++) {
  1096.     for (j = 0; j < f->numedges; j++) {
  1097.       k = bspMem->dsurfedges[f->firstedge + j];
  1098.       if (k < 0) {
  1099.     e = &edgeshare[-k];
  1100.     e->faces[1] = f;
  1101.       }
  1102.       else {
  1103.     e = &edgeshare[k];
  1104.     e->faces[0] = f;
  1105.       }
  1106.  
  1107.       if (e->faces[0] && e->faces[1]) {
  1108.     // determine if coplanar
  1109.     if (e->faces[0]->planenum == e->faces[1]->planenum)
  1110.       e->coplanar = TRUE;
  1111.       }
  1112.     }
  1113.   }
  1114.   
  1115.   tfree(edgeshare);
  1116. }
  1117.  
  1118. /*
  1119.  * ===============
  1120.  * AllocTriangulation
  1121.  * ===============
  1122.  */
  1123. struct triangulation *AllocTriangulation(register struct dplane_t *plane) {
  1124.   struct triangulation *t ;
  1125.   if(!(t = (struct triangulation *)tmalloc(sizeof(struct triangulation))))
  1126.     Error("AllocTriangulation: failed to allocate triangulation!\n");
  1127.   t->plane = plane;
  1128.   return t;
  1129. }
  1130.  
  1131. /*
  1132.  * ===============
  1133.  * FreeTriangulation
  1134.  * ===============
  1135.  */
  1136. void FreeTriangulation(register struct triangulation *trian) {
  1137.   if(trian->matrixsquare)
  1138.     tfree(trian->edgematrix);
  1139.   if(trian->numedges)
  1140.     tfree(trian->edges);
  1141.   if(trian->numpoints)
  1142.     tfree(trian->points);
  1143.   if(trian->numtris)
  1144.     tfree(trian->tris);
  1145.   tfree(trian);
  1146. }
  1147.  
  1148. struct triedge *FindTriEdge(register struct triangulation * trian, register int p0, register int p1)
  1149. {
  1150.   struct triedge *e, *be;
  1151.   vec3_t v1;
  1152.   vec3_t normal;
  1153.   vec_t dist;
  1154.  
  1155.   // recalculation
  1156.   if((trian->matrixsquare < p0) || (trian->matrixsquare < p1)) {
  1157.     struct triedge **newtrie;
  1158.     int i, newsquare = p0 > p1 ? p0 : p1;
  1159.     unsigned char *new, *old;
  1160.     
  1161.     if(!(newtrie = (struct triedge **)tmalloc(newsquare * newsquare * sizeof(struct triedge *))))
  1162.       Error("FindTriEdge: failed to allocate triedges!\n");
  1163.     
  1164.     new = (unsigned char *)newtrie;
  1165.     old = (unsigned char *)trian->edgematrix;
  1166.     
  1167.     for(i = 0; i < trian->matrixsquare; i++) {
  1168.       memcpy(new + (i * newsquare), old + (i * trian->matrixsquare), trian->matrixsquare * sizeof(struct triedge *));
  1169.     }
  1170.     
  1171.     tfree(trian->edgematrix);
  1172.     trian->edgematrix = newtrie;
  1173.     trian->matrixsquare = newsquare;
  1174.   }
  1175.   else if (trian->edgematrix[(p0 * trian->matrixsquare) + p1])
  1176.     return trian->edgematrix[(p0 * trian->matrixsquare) + p1];
  1177.  
  1178.   if (trian->numedges > MAX_TRI_EDGES - 2)
  1179.     Error("trian->numedges > MAX_TRI_EDGES-2");
  1180.  
  1181.   VectorSubtract(trian->points[p1]->origin, trian->points[p0]->origin, v1);
  1182.   VectorNormalize(v1);
  1183.   CrossProduct(v1, trian->plane->normal, normal);
  1184.   dist = DotProduct(trian->points[p0]->origin, normal);
  1185.  
  1186.   if(!(trian->edges = (struct triedge *)trealloc(trian->edges, (trian->numedges + 2) * sizeof(struct triedge))))
  1187.     Error("FindTriEdge: failed to allocate triedges!\n");
  1188.  
  1189.   e = &trian->edges[trian->numedges];
  1190.   e->p0 = p0;
  1191.   e->p1 = p1;
  1192.   e->tri = NULL;
  1193.   VectorCopy(normal, e->normal);
  1194.   e->dist = dist;
  1195.   trian->numedges++;
  1196.   trian->edgematrix[(p0 * trian->matrixsquare) + p1] = e;
  1197.  
  1198.   be = &trian->edges[trian->numedges];
  1199.   be->p0 = p1;
  1200.   be->p1 = p0;
  1201.   be->tri = NULL;
  1202.   VectorNegateTo(normal, be->normal);
  1203.   be->dist = -dist;
  1204.   trian->numedges++;
  1205.   trian->edgematrix[(p1 * trian->matrixsquare) + p0] = be;
  1206.  
  1207.   return e;
  1208. }
  1209.  
  1210. struct triangle *AllocTriangle(register struct triangulation *trian) {
  1211.   if(!(trian->tris = (struct triangle *)trealloc(trian->tris, ++trian->numtris * sizeof(struct triangle))))
  1212.     Error("AllocTriangle: failed to allocate triangle!\n");
  1213.   return trian->tris + trian->numtris - 1;
  1214. }
  1215.  
  1216. /*
  1217.  * ============
  1218.  * TriEdge_r
  1219.  * ============
  1220.  */
  1221. void TriEdge_r(register struct triangulation * trian, register struct triedge * e)
  1222. {
  1223.   int i, bestp = 0;
  1224.   vec3_t v1, v2;
  1225.   vec_t *p0, *p1, *p;
  1226.   vec_t best, ang;
  1227.   struct triangle *nt;
  1228.  
  1229.   if (e->tri)
  1230.     return;                                       // allready connected by someone
  1231.  
  1232.   // find the point with the best angle
  1233.   p0 = trian->points[e->p0]->origin;
  1234.   p1 = trian->points[e->p1]->origin;
  1235.   best = 1.1;
  1236.   for (i = 0; i < trian->numpoints; i++) {
  1237.     p = trian->points[i]->origin;
  1238.     // a 0 dist will form a degenerate triangle
  1239.     if (DotProduct(p, e->normal) - e->dist < 0)
  1240.       continue;                                       // behind edge
  1241.  
  1242.     VectorSubtract(p0, p, v1);
  1243.     VectorSubtract(p1, p, v2);
  1244.     if (!VectorNormalize(v1))
  1245.       continue;
  1246.     if (!VectorNormalize(v2))
  1247.       continue;
  1248.     ang = DotProduct(v1, v2);
  1249.     if (ang < best) {
  1250.       best = ang;
  1251.       bestp = i;
  1252.     }
  1253.   }
  1254.   if (best >= 1)
  1255.     return;                                       // edge doesn't match anything
  1256.  
  1257.   // make a new triangle
  1258.   nt = AllocTriangle(trian);
  1259.   nt->edges[0] = e;
  1260.   nt->edges[1] = FindTriEdge(trian, e->p1, bestp);
  1261.   nt->edges[2] = FindTriEdge(trian, bestp, e->p0);
  1262.   for (i = 0; i < 3; i++)
  1263.     nt->edges[i]->tri = nt;
  1264.   TriEdge_r(trian, FindTriEdge(trian, bestp, e->p1));
  1265.   TriEdge_r(trian, FindTriEdge(trian, e->p0, bestp));
  1266. }
  1267.  
  1268. /*
  1269.  * ============
  1270.  * TriangulatePoints
  1271.  * ============
  1272.  */
  1273. void TriangulatePoints(register struct triangulation * trian)
  1274. {
  1275.   vec_t d, bestd;
  1276.   vec3_t v1;
  1277.   int bp1 = 0, bp2 = 0, i, j;
  1278.   vec_t *p1, *p2;
  1279.   struct triedge *e, *e2;
  1280.  
  1281.   if (trian->numpoints < 2)
  1282.     return;
  1283.  
  1284.   // find the two closest points
  1285.   bestd = 9999;
  1286.   for (i = 0; i < trian->numpoints; i++) {
  1287.     p1 = trian->points[i]->origin;
  1288.     for (j = i + 1; j < trian->numpoints; j++) {
  1289.       p2 = trian->points[j]->origin;
  1290.       VectorSubtract(p2, p1, v1);
  1291.       d = VectorLength(v1);
  1292.       if (d < bestd) {
  1293.     bestd = d;
  1294.     bp1 = i;
  1295.     bp2 = j;
  1296.       }
  1297.     }
  1298.   }
  1299.  
  1300.   e = FindTriEdge(trian, bp1, bp2);
  1301.   e2 = FindTriEdge(trian, bp2, bp1);
  1302.   TriEdge_r(trian, e);
  1303.   TriEdge_r(trian, e2);
  1304. }
  1305.  
  1306. /*
  1307.  * ===============
  1308.  * AddPointToTriangulation
  1309.  * ===============
  1310.  */
  1311. void AddPointToTriangulation(register struct patch *patch, register struct triangulation *trian) {
  1312.   if(!(trian->points = (struct patch **)trealloc(trian->points, ++trian->numpoints * sizeof(struct patch *))))
  1313.     Error("AddPointToTriangulation: failed to allocate point!\n");
  1314.   trian->points[trian->numpoints - 1] = patch;
  1315. }
  1316.  
  1317. /*
  1318.  * ===============
  1319.  * LerpTriangle
  1320.  * ===============
  1321.  */
  1322. void LerpTriangle(register struct triangulation * trian, register struct triangle * t, vec3_t point, vec3_t color)
  1323. {
  1324.   struct patch *p1, *p2, *p3;
  1325.   vec3_t base, d1, d2;
  1326.   float x, y, x1, y1, x2, y2;
  1327.  
  1328.   p1 = trian->points[t->edges[0]->p0];
  1329.   p2 = trian->points[t->edges[1]->p0];
  1330.   p3 = trian->points[t->edges[2]->p0];
  1331.  
  1332.   VectorCopy(p1->totallight, base);
  1333.   VectorSubtract(p2->totallight, base, d1);
  1334.   VectorSubtract(p3->totallight, base, d2);
  1335.  
  1336.   x = DotProduct(point, t->edges[0]->normal) - t->edges[0]->dist;
  1337.   y = DotProduct(point, t->edges[2]->normal) - t->edges[2]->dist;
  1338.  
  1339.   x1 = 0;
  1340.   y1 = DotProduct(p2->origin, t->edges[2]->normal) - t->edges[2]->dist;
  1341.  
  1342.   x2 = DotProduct(p3->origin, t->edges[0]->normal) - t->edges[0]->dist;
  1343.   y2 = 0;
  1344.  
  1345.   if (fabs(y1) < ON_EPSILON || fabs(x2) < ON_EPSILON) {
  1346.     VectorCopy(base, color);
  1347.     return;
  1348.   }
  1349.  
  1350.   VectorMA(base, x / x2, d2, color);
  1351.   VectorMA(color, y / y1, d1, color);
  1352. }
  1353.  
  1354. bool PointInTriangle(vec3_t point, register struct triangle * t)
  1355. {
  1356.   int i;
  1357.   struct triedge *e;
  1358.   vec_t d;
  1359.  
  1360.   for (i = 0; i < 3; i++) {
  1361.     e = t->edges[i];
  1362.     d = DotProduct(e->normal, point) - e->dist;
  1363.     if (d < 0)
  1364.       return FALSE;                                   // not inside
  1365.  
  1366.   }
  1367.  
  1368.   return TRUE;
  1369. }
  1370.  
  1371. /*
  1372.  * ===============
  1373.  * SampleTriangulation
  1374.  * ===============
  1375.  */
  1376. void SampleTriangulation(vec3_t point, register struct triangulation * trian, vec3_t color)
  1377. {
  1378.   struct triangle *t;
  1379.   struct triedge *e;
  1380.   vec_t d, best;
  1381.   struct patch *p0, *p1;
  1382.   vec3_t v1, v2;
  1383.   int i, j;
  1384.  
  1385.   if (trian->numpoints == 0) {
  1386.     VectorClear(color);
  1387.     return;
  1388.   }
  1389.   if (trian->numpoints == 1) {
  1390.     VectorCopy(trian->points[0]->totallight, color);
  1391.     return;
  1392.   }
  1393.  
  1394.   // search for triangles
  1395.   for (t = trian->tris, j = 0; j < trian->numtris; t++, j++) {
  1396.     if (!PointInTriangle(point, t))
  1397.       continue;
  1398.  
  1399.     // this is it
  1400.     LerpTriangle(trian, t, point, color);
  1401.     return;
  1402.   }
  1403.  
  1404.   // search for exterior edge
  1405.   for (e = trian->edges, j = 0; j < trian->numedges; e++, j++) {
  1406.     if (e->tri)
  1407.       continue;                                       // not an exterior edge
  1408.  
  1409.     d = DotProduct(point, e->normal) - e->dist;
  1410.     if (d < 0)
  1411.       continue;                                       // not in front of edge
  1412.  
  1413.     p0 = trian->points[e->p0];
  1414.     p1 = trian->points[e->p1];
  1415.  
  1416.     VectorSubtract(p1->origin, p0->origin, v1);
  1417.     VectorNormalize(v1);
  1418.     VectorSubtract(point, p0->origin, v2);
  1419.     d = DotProduct(v2, v1);
  1420.     if (d < 0)
  1421.       continue;
  1422.     if (d > 1)
  1423.       continue;
  1424.     for (i = 0; i < 3; i++)
  1425.       color[i] = p0->totallight[i] + d * (p1->totallight[i] - p0->totallight[i]);
  1426.     return;
  1427.   }
  1428.  
  1429.   // search for nearest point
  1430.   best = 99999;
  1431.   p1 = NULL;
  1432.   for (j = 0; j < trian->numpoints; j++) {
  1433.     p0 = trian->points[j];
  1434.     VectorSubtract(point, p0->origin, v1);
  1435.     d = VectorLength(v1);
  1436.     if (d < best) {
  1437.       best = d;
  1438.       p1 = p0;
  1439.     }
  1440.   }
  1441.  
  1442.   if (!p1)
  1443.     Error("SampleTriangulation: no points");
  1444.  
  1445.   VectorCopy(p1->totallight, color);
  1446. }
  1447.  
  1448. /*
  1449.  * =============
  1450.  * GatherSampleLight
  1451.  * 
  1452.  * Lightscale is the normalizer for multisampling
  1453.  * =============
  1454.  */
  1455. void GatherSampleLight(__memBase, vec3_t pos, vec3_t normal,
  1456.                register float **styletable, register int offset, register int mapsize, register float lightscale)
  1457. {
  1458.   int i;
  1459.   struct directlight *l;
  1460.   unsigned char pvs[(MAX_MAP_LEAFS + 7) / 8];
  1461.   vec3_t delta;
  1462.   float dot, dot2;
  1463.   float dist;
  1464.   float scale = 1.0;
  1465.   float *dest;
  1466.  
  1467.   // get the PVS for the pos to limit the number of checks
  1468.   if (!PvsForOrigin(bspMem, pos, pvs)) {
  1469.     return;
  1470.   }
  1471.  
  1472.   for (i = 0; i < bspMem->numleafs; i++) {
  1473.     if ((pvs[i >> 3] & (1 << (i & 7)))) {
  1474.       for (l = directlights[i]; l; l = l->next) {
  1475.         VectorSubtract(l->origin, pos, delta);
  1476.         dist = VectorNormalize(delta);
  1477.         dot = DotProduct(delta, normal);
  1478.         if (dot <= 0.001)
  1479.       continue;                                   // behind sample surface
  1480.         switch (l->type) {
  1481.       case emit_point:
  1482.         // linear falloff
  1483.         scale = (l->intensity - dist) * dot;
  1484.         break;
  1485.  
  1486.       case emit_surface:
  1487.         dot2 = -DotProduct(delta, l->normal);
  1488.         if (dot2 <= 0.001)
  1489.           goto skipadd;                               // behind light surface
  1490.         scale = (l->intensity / (dist * dist)) * dot * dot2;
  1491.         break;
  1492.  
  1493.       case emit_spotlight:
  1494.         // linear falloff
  1495.         dot2 = -DotProduct(delta, l->normal);
  1496.         if (dot2 <= l->stopdot)
  1497.           goto skipadd;                               // outside light cone
  1498.         scale = (l->intensity - dist) * dot;
  1499.         break;
  1500.       default:
  1501.         Error("Bad l->type");
  1502.         }
  1503.  
  1504.         if (TestLine_r(0, pos, l->origin))
  1505.       continue;                                   // occluded
  1506.         if (scale <= 0)
  1507.       continue;
  1508.  
  1509.         // if this style doesn't have a table yet, allocate one
  1510.         if (!styletable[l->style])
  1511.       styletable[l->style] = (float *)tmalloc(mapsize);
  1512.  
  1513.         dest = styletable[l->style] + offset;
  1514.         // add some light to it
  1515.         VectorMA(dest, scale * lightscale, l->color, dest);
  1516.  
  1517.       skipadd:;
  1518.       }
  1519.     }
  1520.     /** mprogress(bspMem->numleafs, i + 1); **/
  1521.   }
  1522.  
  1523. }
  1524.  
  1525. /*
  1526.  * =============
  1527.  * FinalLightFace
  1528.  * 
  1529.  * Add the indirect lighting on top of the direct
  1530.  * lighting and save into final map format
  1531.  * =============
  1532.  */
  1533. void FinalLightFace(__memBase, register int facenum)
  1534. {
  1535.   struct dface_t *f;
  1536.   int i, j, k, st;
  1537.   vec3_t lb;
  1538.   struct patch *patch;
  1539.   struct triangulation *trian = 0;
  1540.   struct facelight *fl;
  1541.   float minlight;
  1542.   float max, newmax;
  1543.   unsigned char *dest;
  1544.   int pfacenum;
  1545.   vec3_t facemins, facemaxs;
  1546.  
  1547.   f = &bspMem->dfaces[facenum];
  1548.   fl = &facelights[facenum];
  1549.  
  1550. /** added waterlit **/
  1551.   if ((bspMem->texinfo[f->texinfo].flags & TEX_SPECIAL)) {               // non-lit texture
  1552.     if(bspMem->litOptions & LIGHT_WATERLIT) {
  1553.       int *textures = (int *)(bspMem->dtexdata + 4);
  1554.       struct mipmap *tex = (struct mipmap *)(bspMem->dtexdata + textures[bspMem->texinfo[f->texinfo].miptex]);
  1555.       if(!strcmp(tex->name, "sky"))
  1556.         return;
  1557.     }
  1558.     else
  1559.       return;
  1560.   }
  1561.  
  1562.   if(bspMem->lightdatasize + (fl->numstyles * (fl->numsamples * 3)) >= bspMem->max_lightdatasize)
  1563.     ExpandClusters(bspMem, LUMP_LIGHTING);
  1564.   f->lightofs = bspMem->lightdatasize;
  1565.   bspMem->lightdatasize += fl->numstyles * (fl->numsamples * 3);
  1566.  
  1567.   f->styles[0] = 0;
  1568.   f->styles[1] = f->styles[2] = f->styles[3] = 0xff;
  1569.  
  1570.   //
  1571.   // set up the triangulation
  1572.   //
  1573.   if (numbounce > 0) {
  1574.     ClearLBounds(facemins, facemaxs);
  1575.     for (i = 0; i < f->numedges; i++) {
  1576.       int ednum = bspMem->dsurfedges[f->firstedge + i];
  1577.       if (ednum >= 0)
  1578.     AddPointToBounds(bspMem->dvertexes[bspMem->dedges[ednum].v[0]].point, facemins, facemaxs);
  1579.       else
  1580.     AddPointToBounds(bspMem->dvertexes[bspMem->dedges[-ednum].v[1]].point, facemins, facemaxs);
  1581.     }
  1582.  
  1583.     trian = AllocTriangulation(&bspMem->dplanes[f->planenum]);
  1584.  
  1585.     // for all faces on the plane, add the nearby patches
  1586.     // to the triangulation
  1587.     for (pfacenum = planelinks[f->side][f->planenum];
  1588.      pfacenum; pfacenum = facelinks[pfacenum]) {
  1589.       for (patch = facepatches[pfacenum]; patch; patch = patch->next) {
  1590.     for (i = 0; i < 3; i++) {
  1591.       if (facemins[i] - patch->origin[i] > subdiv * 2)
  1592.         break;
  1593.       if (patch->origin[i] - facemaxs[i] > subdiv * 2)
  1594.         break;
  1595.     }
  1596.     if (i != 3)
  1597.       continue;                                   // not needed for this face
  1598.     AddPointToTriangulation(patch, trian);
  1599.       }
  1600.     }
  1601.     //for (i = 0; i < trian->numpoints; i++)
  1602.     //  memset(trian->edgematrix[i], 0, trian->numpoints * sizeof(trian->edgematrix[0][0]));
  1603.     TriangulatePoints(trian);
  1604.   }
  1605.  
  1606.   //
  1607.   // sample the triangulation
  1608.   //
  1609.  
  1610.   // _minlight allows models that have faces that would not be
  1611.   // illuminated to receive a mottled light pattern instead of
  1612.   // black
  1613.   minlight = FloatForKey(faceentity[facenum], "_minlight") * 128;
  1614.  
  1615.   dest = &bspMem->dlightdata[f->lightofs];
  1616.  
  1617.   if (fl->numstyles > MAXLIGHTMAPS) {
  1618.     fl->numstyles = MAXLIGHTMAPS;
  1619.     eprintf("face with too many lightstyles: (%g %g %g)\n",
  1620.         facepatches[facenum]->origin[0],
  1621.         facepatches[facenum]->origin[1],
  1622.         facepatches[facenum]->origin[2]);
  1623.   }
  1624.  
  1625.   for (st = 0; st < fl->numstyles; st++) {
  1626.     f->styles[st] = fl->stylenums[st];
  1627.     for (j = 0; j < fl->numsamples; j++) {
  1628.       VectorCopy((fl->samples[st] + j * 3), lb);
  1629.       if (numbounce > 0 && st == 0) {
  1630.     vec3_t add;
  1631.  
  1632.     SampleTriangulation(fl->origins + j * 3, trian, add);
  1633.     VectorAdd(lb, add, lb);
  1634.       }
  1635.       // add an ambient term if desired
  1636.       lb[0] += ambient;
  1637.       lb[1] += ambient;
  1638.       lb[2] += ambient;
  1639.  
  1640.       VectorScale(lb, lightscale, lb);
  1641.  
  1642.       // we need to clamp without allowing hue to change
  1643.       for (k = 0; k < 3; k++)
  1644.     if (lb[k] < 1)
  1645.       lb[k] = 1;
  1646.       max = lb[0];
  1647.       if (lb[1] > max) max = lb[1];
  1648.       if (lb[2] > max) max = lb[2];
  1649.       newmax = max;
  1650.       if (newmax < 0)
  1651.     newmax = 0;                                   // roundoff problems
  1652.  
  1653.       if (newmax < minlight) {
  1654.     newmax = minlight + (rand() % 48);
  1655.       }
  1656.       if (newmax > maxlight)
  1657.     newmax = maxlight;
  1658.  
  1659.       for (k = 0; k < 3; k++) {
  1660.     *dest++ = lb[k] * newmax / max;
  1661.       }
  1662.     }
  1663.   }
  1664.  
  1665.   if (numbounce > 0)
  1666.     FreeTriangulation(trian);
  1667. }
  1668.  
  1669. /*
  1670.  * =============
  1671.  * RadFace
  1672.  * =============
  1673.  */
  1674. float sampleofs[5][2] =
  1675. {
  1676.   {0, 0},
  1677.   {-0.25, -0.25},
  1678.   {0.25, -0.25},
  1679.   {0.25, 0.25},
  1680.   {-0.25, 0.25}};
  1681.  
  1682. void RadFace(__memBase, register int facenum)
  1683. {
  1684.   struct dface_t *f;
  1685.   struct lightinfo l[5];
  1686.   float *styletable[MAX_LSTYLES];
  1687.   int i, j;
  1688.   float *spot;
  1689.   struct patch *patch;
  1690.   int numsamples;
  1691.   int tablesize;
  1692.   struct facelight *fl;
  1693.  
  1694.   f = &bspMem->dfaces[facenum];
  1695.  
  1696. /** added waterlit **/
  1697.   if ((bspMem->texinfo[f->texinfo].flags & TEX_SPECIAL)) {               // non-lit texture
  1698.     if(bspMem->litOptions & LIGHT_WATERLIT) {
  1699.       int *textures = (int *)(bspMem->dtexdata + 4);
  1700.       struct mipmap *tex = (struct mipmap *)(bspMem->dtexdata + textures[bspMem->texinfo[f->texinfo].miptex]);
  1701.       if(!strcmp(tex->name, "sky"))
  1702.         return;
  1703.     }
  1704.     else
  1705.       return;
  1706.   }
  1707.   memset(styletable, 0, sizeof(styletable));
  1708.  
  1709.   if (bspMem->litOptions & LIGHT_EXTRA)
  1710.     numsamples = 5;
  1711.   else
  1712.     numsamples = 1;
  1713.     
  1714.   for (i = 0; i < numsamples; i++) {
  1715.     memset(&l[i], 0, sizeof(l[i]));
  1716.     l[i].surfnum = facenum;
  1717.     l[i].face = f;
  1718.     VectorCopy(bspMem->dplanes[f->planenum].normal, l[i].facenormal);
  1719.     l[i].facedist = bspMem->dplanes[f->planenum].dist;
  1720.     if (f->side) {
  1721.       VectorNegate(l[i].facenormal);
  1722.       l[i].facedist = -l[i].facedist;
  1723.     }
  1724.  
  1725.     // get the origin offset for rotating bmodels
  1726.     VectorCopy(faceoffset[facenum], l[i].modelorg);
  1727.  
  1728.     CalcFaceVectors(bspMem, &l[i]);
  1729.     CalcFaceExtentsII(bspMem, &l[i]);
  1730.     CalcPoints(bspMem, &l[i], sampleofs[i][0], sampleofs[i][1]);
  1731.   }
  1732.  
  1733.   tablesize = l[0].numsurfpt * sizeof(vec3_t);
  1734.   styletable[0] = (float *)tmalloc(tablesize);
  1735.  
  1736.   fl = &facelights[facenum];
  1737.   fl->numsamples = l[0].numsurfpt;
  1738.   fl->origins = (float *)tmalloc(tablesize);
  1739.   memcpy(fl->origins, l[0].surfpt, tablesize);
  1740.  
  1741.   for (i = 0; i < l[0].numsurfpt; i++) {
  1742.     for (j = 0; j < numsamples; j++)
  1743.       GatherSampleLight(bspMem, l[j].surfpt[i], l[0].facenormal, styletable, i * 3, tablesize, 1.0 / numsamples);
  1744.     // contribute the sample to one or more patches
  1745.     AddSampleToPatch(l[0].surfpt[i], styletable[0] + i * 3, facenum);
  1746.   }
  1747.  
  1748.   // average up the direct light on each patch for radiosity
  1749.   for (patch = facepatches[facenum]; patch; patch = patch->next) {
  1750.     if (patch->samples)
  1751.       VectorScale(patch->samplelight, 1.0 / patch->samples, patch->samplelight);
  1752.   }
  1753.  
  1754.   for (i = 0; i < MAX_LSTYLES; i++) {
  1755.     if (!styletable[i])
  1756.       continue;
  1757.     if (fl->numstyles == MAX_STYLES)
  1758.       break;
  1759.     fl->samples[fl->numstyles] = styletable[i];
  1760.     fl->stylenums[fl->numstyles] = i;
  1761.     fl->numstyles++;
  1762.   }
  1763.  
  1764.   // the light from DIRECT_LIGHTS is sent out, but the
  1765.   // texture itself should still be full bright
  1766.   if (facepatches[facenum]->baselight[0] >= DIRECT_LIGHT ||
  1767.       facepatches[facenum]->baselight[1] >= DIRECT_LIGHT ||
  1768.       facepatches[facenum]->baselight[2] >= DIRECT_LIGHT) {
  1769.     spot = fl->samples[0];
  1770.     for (i = 0; i < l[0].numsurfpt; i++, spot += 3)
  1771.       VectorAdd(spot, facepatches[facenum]->baselight, spot);
  1772.   }
  1773. }
  1774.  
  1775. /*
  1776.  * =============
  1777.  * RadWorld
  1778.  * =============
  1779.  */
  1780. void RadWorld(__memBase) {
  1781.   int back, i;
  1782.  
  1783. mprintf("CalcTR\n");
  1784.   CalcTextureReflectivity(bspMem);
  1785. mprintf("MakeMB\n");
  1786.   MakeBackPlanes(bspMem);
  1787. mprintf("MakeP\n");
  1788.   MakeParents(bspMem, 0, -1);
  1789.   // turn each face into a single patch
  1790. mprintf("MakePa\n");
  1791.   MakePatches(bspMem);
  1792.   // subdivide patches to a maximum dimension
  1793. mprintf("SubD\n");
  1794.   SubdividePatches(bspMem);
  1795.   mprintf("%5i patches\n", numpatches);
  1796.   // create directlights out of patches and lights
  1797. mprintf("CreateDL\n");
  1798.   CreateDirectLights(bspMem);
  1799.   mprintf("%5i patches\n", numpatches);
  1800.   back = numpatches;
  1801.   for (i = 0; i < bspMem->numfaces; i++, bspfileface++) {
  1802.     RadFace(bspMem, i);
  1803.     mprogress(bspMem->numfaces, i + 1);
  1804.   }
  1805.   mprintf("%5i patches: %d\n", numpatches);
  1806.   numpatches = back;
  1807.   mprintf("%5i patches: %d\n", numpatches);
  1808.   if (numbounce > 0) {
  1809.     // build transfer lists
  1810. mprintf("MakeTr\n");
  1811.     for (i = 0; i < numpatches; i++)
  1812.       MakeTransfers(bspMem, i);
  1813.  
  1814.     mprintf("transfer lists: %g megs\n",(float)total_transfer * sizeof(struct transfer) / (1024 * 1024));
  1815.     // spread light around
  1816. mprintf("Bounce\n");
  1817.     BounceLight();
  1818. mprintf("FreeTr\n");
  1819.     FreeTransfers();
  1820. mprintf("CheckP\n");
  1821.     CheckPatches();
  1822.   }
  1823.   // blend bounced light into direct light and save
  1824. mprintf("PairEd\n");
  1825.   PairEdges(bspMem);
  1826. mprintf("LinkPl\n");
  1827.   LinkPlaneFaces(bspMem);
  1828.   bspMem->lightdatasize = 0;
  1829.   for (i = 0; i < bspMem->numfaces; i++) {
  1830.     FinalLightFace(bspMem, i);
  1831.     mprogress(bspMem->numfaces, i + 1);
  1832.   }
  1833. }
  1834.  
  1835.